package com.sicheng.lc.周赛.分类.dp.数位;

import java.util.ArrayList;

/**
 * @author zsc
 * @version 1.0
 * @date 2022/8/18 21:32
 */
@SuppressWarnings("all")
public class 至少有1位重复的数字 {
    //https://leetcode.cn/problems/numbers-with-repeated-digits/
    static int N = 10;
    static int[][] c = new int[N + 1][N + 1];
    static int[][] a = new int[N + 1][N + 1];
    static int[] f = new int[N + 1];
    static int[] d = new int[N + 1];

    static {
        c[0][0] = 1;
        f[0] = 1;
        // 初始化 阶乘数
        for (int i = 1; i <= N; i++) {
            f[i] = f[i - 1] * i;
        }
        // 初始化排列数和组合数 A[i,j],C[i,j]
        for (int i = 1; i <= N; i++) {
            for (int j = 0; j <= i; j++) {
                if (j == 0)
                    c[i][j] = 1;
                else
                    c[i][j] = c[i - 1][j] + c[i - 1][j - 1];
                a[i][j] = c[i][j] * f[j];
            }
        }
        // 初始化 有前导0时 低位填不同数字的情况
        // 比如 ____ 1_ 一共有6位，前4位前导0 [1,9]里选1个填到开头的 低i位 从剩余9数字里选 i-1位全排列
        for (int i = 1; i <= 10; i++) {
            // d[i] 表示低i位开始填数，前面的高位是前导0不填
            d[i] = d[i - 1] + c[9][1] * a[9][i - 1];
        }

    }


    public int f(int n) {
        ArrayList<Integer> nums = new ArrayList<>();
        while (n != 0) {
            nums.add(n % 10);
            n /= 10;
        }
        // 前面已经填了数的信息 压缩到32位的int里
        int mask = 0;
        int res = 0;
        for (int i = nums.size() - 1; i >= 0; i--) {
            int x = nums.get(i);
            for (int j = i == nums.size() - 1 ? 1 : 0; j < x; j++) {
                // 当前位填的j不可以和mask冲突 也就是以前填了当前不可以再填
                if ((mask >> j & 1) == 0)
                    // 当前要填的包含 第i在内一共i+1 位
                    // [0,9] 里选了mask和当前的j 剩余的数字里选i个出来全排列 因为还剩i位要填
                    res += a[N - (nums.size() - i)][i];
            }

            // 当前位是否可以填到 x
            if ((mask >> x & 1) == 1)
                break;
            mask |= 1 << x;
            if (i == 0)
                res++;
        }

        // 特判前导0 提前预处理到d
        //for (int i = 1; i < nums.size(); i++) {
        //   res += c[9][1] * a[9][i - 1];
        //}
        res += d[nums.size() - 1];
        return res;
    }

    public int numDupDigitsAtMostN(int n) {
        return n - f(n);
    }
}
